package 剑指;

/**
 * @author : zx
 * @version V1.0
 */
public class a3_13机器人的运动范围 {

    static class Solution {

        private boolean[][] flags;
        private int rowLen;
        private int legLen;

        public int movingCount(int m, int n, int k) {
            flags = new boolean[m][n];
            rowLen = m;
            legLen = n;
            flags[0][0] = true;
            return 1+goAround(0, 0, k);
        }

        public int goAround(int r, int l, int k){
            int sum = 0;
            if(r+1 < rowLen && !flags[r+1][l] && getSum(r+1)+getSum(l)<=k){
                flags[r+1][l] = true;
                sum += 1 + goAround(r+1, l, k);
            }
            if(r-1 >= 0 && !flags[r-1][l] && getSum(r-1)+getSum(l)<=k){
                flags[r-1][l] = true;
                sum += 1 + goAround(r-1, l, k);
            }
            if(l+1 < legLen && !flags[r][l+1] && getSum(r)+getSum(l+1)<=k){
                flags[r][l+1] = true;
                sum += 1 + goAround(r, l+1, k);
            }
            if(l-1 >= 0 && !flags[r][l-1] && getSum(r)+getSum(l-1)<=k){
                flags[r][l-1] = true;
                sum += 1 + goAround(r, l-1, k);
            }
            return sum;
        }

        public int getSum(int row){
            int sum = 0;
            sum += row % 10;
            while ((row  /= 10) != 0){
                sum += row % 10;
            }
            return sum;
        }
    }

    public static void main(String[] args){
        Solution s = new Solution();
        System.out.println(s.movingCount(2,3,1));
    }
}
